package org.leetcode.middle.leetcode494;

public class Solution {
    int count = 0;
    public int findTargetSumWays(int[] nums, int target) {
        backtracking(nums,0,0,target);
        return count;
    }

    private void backtracking(int[] nums, int index, int sum, int target) {
        if (index == nums.length) {
            if (sum == target) {
                count++;
            }
            return;
        }

        sum = sum + nums[index];
        backtracking(nums, index + 1, sum, target);
        sum = sum - nums[index];

        sum = sum - nums[index];
        backtracking(nums,index+1,sum,target);
        sum = sum + nums[index];
    }
}
